Exercici 10 (Tasca 7).
(NP,
P,
3SAT)
Pertanyen a \mathsf{P}?
Demostreu que els llenguatges següents sobre grafs no dirigits són a \mathsf{NP}. Quins pertanyen a \mathsf{P}?
- Dos coloració. \mathtt{2COL} = \{ G \mid el graf G té una 2-coloració\}, on una k-coloració de G és una assignació d’un nombre a \{1,\dots,k\} a cada vèrtex de G tal que tot parell de vèrtexs adjacents rep colors diferents.
- Tres coloració. \mathtt{3COL} = \{ G \mid el graf G té una 3-coloració\}.
- Camí hamiltonià. \mathtt{HP} = \{ G \mid el graf G té un camí hamiltonià\}, on un camí se’n diu hamiltonià si visita cada vèrtex exactament un cop.
- Connectivitat. \mathtt{CONNECTED} =\{ G \mid G és un graf connex\}.